package tree;

import java.util.ArrayList;
import java.util.List;

// B+ 树节点类
class BPlusTreeNode {
    int[] keys; // 存储键的数组
    int t; // 阶
    boolean isLeaf; // 是否为叶子节点
    BPlusTreeNode[] children; // 子节点指针数组
    BPlusTreeNode next; // 叶子节点链表中的下一个节点指针
    int n; // 节点中当前的键的数量

    public BPlusTreeNode(int t, boolean isLeaf) {
        this.t = t;
        this.isLeaf = isLeaf;
        this.keys = new int[2 * t];
        this.children = new BPlusTreeNode[2 * t + 1];
        this.n = 0;
    }
}

// B+ 树类
public class BPlusTree {
    BPlusTreeNode root; // 树的根节点
    int t; // 阶

    public BPlusTree(int t) {
        this.root = new BPlusTreeNode(t, true);
        this.t = t;
    }

    // 插入一个键
    public void insert(int key) {
        BPlusTreeNode r = root;
        if (r.n == 2 * t) {
            // 如果根节点已满，需要分裂根节点
            BPlusTreeNode s = new BPlusTreeNode(t, false);
            s.children[0] = r;
            splitChild(s, 0);
            root = s;
        }
        insertNonFull(root, key);
    }

    // 分裂子节点
    private void splitChild(BPlusTreeNode parent, int i) {
        BPlusTreeNode y = parent.children[i];
        BPlusTreeNode z = new BPlusTreeNode(t, y.isLeaf);
        z.n = t;

        // 将 y 的后半部分键复制到 z 中
        for (int j = 0; j < t; j++) {
            z.keys[j] = y.keys[j + t];
        }

        if (!y.isLeaf) {
            // 如果 y 不是叶子节点，复制子节点指针
            for (int j = 0; j < t + 1; j++) {
                z.children[j] = y.children[j + t];
            }
        } else {
            // 如果 y 是叶子节点，维护叶子链表
            z.next = y.next;
            y.next = z;
        }

        y.n = t; // 更新 y 的键数量

        // 将 z 插入到父节点的子节点指针中
        for (int j = parent.n; j >= i + 1; j--) {
            parent.children[j + 1] = parent.children[j];
        }

        parent.children[i + 1] = z;

        // 将 y 的中间键提升到父节点
        for (int j = parent.n - 1; j >= i; j--) {
            parent.keys[j + 1] = parent.keys[j];
        }

        parent.keys[i] = y.keys[t - 1];
        parent.n++;
    }

    // 在非满节点插入键
    private void insertNonFull(BPlusTreeNode node, int key) {
        int i = node.n - 1;

        if (node.isLeaf) {
            // 如果是叶子节点，直接插入到合适的位置
            while (i >= 0 && key < node.keys[i]) {
                node.keys[i + 1] = node.keys[i];
                i--;
            }
            node.keys[i + 1] = key;
            node.n++;
        } else {
            // 如果是内部节点，找到合适的子节点插入
            while (i >= 0 && key < node.keys[i]) {
                i--;
            }
            i++;
            if (node.children[i].n == 2 * t) {
                // 如果子节点已满，先分裂
                splitChild(node, i);
                if (key > node.keys[i]) {
                    i++;
                }
            }
            insertNonFull(node.children[i], key);
        }
    }

    // 遍历叶子节点
    public void traverseLeaves() {
        BPlusTreeNode current = root;
        // 找到最左边的叶子节点
        while (!current.isLeaf) {
            current = current.children[0];
        }

        // 遍历叶子节点链表
        while (current != null) {
            for (int i = 0; i < current.n; i++) {
                System.out.print(current.keys[i] + " ");
            }
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BPlusTree bptree = new BPlusTree(3);  // 创建一个阶为3的B+树

        // 插入一些键
        bptree.insert(10);
        bptree.insert(20);
        bptree.insert(5);
        bptree.insert(6);
        bptree.insert(12);
        bptree.insert(30);
        bptree.insert(7);
        bptree.insert(17);

        // 遍历叶子节点
        System.out.println("B+树的叶子节点遍历结果：");
        bptree.traverseLeaves();
    }
}
